package com.leetcode;


/**
 * 5. 最长回文子串 (中等)
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 */
public class LeetCode5 {

    public static void main(String[] arg0) {
        String testStr = "a";
        System.out.println("最长回文子串 = " + longestPalindrome(testStr));
    }

    /**
     * 官方题解用了动态规划，实例化了一个 length * length 的布尔型二维数组。
     * 二维数组还是只用斜对角线一半的空间，对角线有 length 个，记录长度是 1 的回文子串。
     * 向左下角逼近，数量逐渐是 length - 1, length - 2, ... , 1。分别对应长度为2, 3, ... length的回文子串数量。
     * 而值也受之前值的影响，例如长度为5的受长度为3的影响，只有收尾相同并且中间部分长度为3的布尔值对应也是true才是回文子串。
     */
    public static String longestPalindrome(String s) {
        int startIndex = 0;
        int endIndex = 1;
        int idx = endIndex - startIndex;
        for (int i = 1; i < s.length(); i++) {
            int left = i, right = i;
            int tempIdx;
            // 这里考虑的是中心是单个字母对称的情况
            while (left > 0 && right < (s.length() - 1) && s.charAt(left - 1) == s.charAt(right + 1)) {
                left--;
                right++;
            }
            tempIdx = right - left + 1;
            if (tempIdx > idx) {
                startIndex = left;
                endIndex = right + 1;
                idx = tempIdx;
            }

            // 要加上中心是两个相同字母的情况，有两种，一个是和左边的字母相同，一个是和右边的字母相同
            if (s.charAt(i - 1) == s.charAt(i)) {
                left = i - 1;
                right = i;
                while (left > 0 && right < (s.length() - 1) && s.charAt(left - 1) == s.charAt(right + 1)) {
                    left--;
                    right++;
                }
                tempIdx = right - left + 1;
                if (tempIdx > idx) {
                    startIndex = left;
                    endIndex = right + 1;
                    idx = tempIdx;
                }
            }

            if (i < (s.length() - 1) && s.charAt(i + 1) == s.charAt(i)) {
                left = i;
                right = i + 1;
                while (left > 0 && right < (s.length() - 1) && s.charAt(left - 1) == s.charAt(right + 1)) {
                    left--;
                    right++;
                }
                tempIdx = right - left + 1;
                if (tempIdx > idx) {
                    startIndex = left;
                    endIndex = right + 1;
                    idx = tempIdx;
                }
            }
        }

        return s.substring(startIndex, endIndex);
    }


}
